package cn.zzf.leetcode;

/**
 * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
 * 算法的时间复杂度应该为 O(log (m+n)) 。
 * <p>
 * 示例 1：<br/>
 * 输入：nums1 = [1,3], nums2 = [2]<br/>
 * 输出：2.00000<br/>
 * 解释：合并数组 = [1,2,3] ，中位数 2<br/>
 * <p>
 * 示例 2：<br/>
 * 输入：nums1 = [1,2], nums2 = [3,4]<br/>
 * 输出：2.50000<br/>
 * 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5<br/>
 * <p>
 * 提示：<br/>
 * nums1.length == m<br/>
 * nums2.length == n<br/>
 * 0 <= m <= 1000<br/>
 * 0 <= n <= 1000<br/>
 * 1 <= m + n <= 2000<br/>
 * -106 <= nums1[i], nums2[i] <= 106<br/>
 */
public class T0004_FindMedianSortedArrays {

    /**
     * 思路：遍历两个数组，比较两个数组中取出的数，小的取出，再取下一个，重复比较。
     * 直到取出的数 的数量 = (nums1.length + nums2.length) / 2 = 中位数的索引位
     */
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int length = nums1.length + nums2.length;
        // 考虑到偶数个时中位数有两个，定义两个变量，奇数时这两个变量值相同。
        int idx1;
        int idx2;
        if (length % 2 == 1) {
            idx1 = idx2 = length / 2;
        } else {
            idx1 = length / 2 - 1;
            idx2 = length / 2;
        }

        int r1 = 0; // 第一个中位数的值
        int r2 = 0; // 第二个中位数的值
        int idx = 0; // 当前已取出的数量，用于计算是否已经可以作为中位数
        int i1 = 0; // 第一个数组取数的索引位
        int i2 = 0; // 第二个数组取数的索引位
        while (idx <= idx2) {
            // 取数，兼容一个数组被取完的情况：1,2,3 + 4,5,6,7,8,9
            int v1 = i1 == nums1.length ? Integer.MAX_VALUE : nums1[i1];
            int v2 = i2 == nums2.length ? Integer.MAX_VALUE : nums2[i2];
            // 比较，谁小取谁，索引位+1
            if (v1 >= v2) {
                // 结果判断，是否已经满足中位数的数量
                if (idx == idx1) r1 = v2;
                if (idx == idx2) r2 = v2;
                i2++;
            } else {
                // 结果判断，是否已经满足中位数的数量
                if (idx == idx1) r1 = v1;
                if (idx == idx2) r2 = v1;
                i1++;
            }
            // 每执行一次，已取出的数量+1
            idx++;
        }
        // 结果计算
        return ((double) (r1 + r2)) / 2;
    }

    public static void main(String[] args) {
        System.out.println(findMedianSortedArrays(new int[]{1, 2, 3}, new int[]{4, 5, 6, 7, 8, 9}));
    }

}
